#include <stdio.h>
#include <stdlib.h>
#include "bilist.h"


int bilist_create_head(Head_st **ptr)
{
	*ptr = malloc(sizeof(**ptr));
	if(*ptr == NULL)
		return -1;
	(*ptr)->first = NULL;
	(*ptr)->last = NULL;
	(*ptr)->number = 0;
	return 0;
}

int bilist_create_list(Head_st **ptr,enum CUR_MODE way)
{
	bilist_st *newnode = NULL;

	while(1)
	{
		int data;
		scanf("%d",&data);
		if(data == -1)
			break;
		newnode = malloc(sizeof(*newnode));
		if(newnode == NULL)
			return -1;
		newnode->data = data;
		newnode->prev = NULL;
		newnode->next = NULL;

		switch(way)
		{
			case HEAD_CUR:
				{
					bilist_insert_head(ptr,newnode);
					break;
				}
			case END_CUR:	
				{
					bilist_insert_end(ptr,newnode);
					break;
				}
			case ORDER_CUR:
				{
					bilist_insert_order(ptr,newnode);
					break;
				}
			default:
				return -1;
		}
	}
	return 0;
}

int bilist_insert_head(Head_st **ptr,bilist_st *newnode)
{
	if((*ptr)->first == NULL)
	{
		(*ptr)->first = newnode;
		(*ptr)->last = newnode;
		//让头结点的last一直指向first
		(*ptr)->last->next = (*ptr)->first;
		(*ptr)->number++;
		newnode->prev = newnode->next = NULL;
	}
	else
	{
		newnode->next = (*ptr)->first;
		(*ptr)->first->prev = newnode;
		(*ptr)->first = newnode;
		(*ptr)->last->next = (*ptr)->first;
		(*ptr)->number++;
	}
	return 0;
}

int bilist_insert_end(Head_st **ptr,bilist_st *newnode)
{
	if((*ptr)->first == NULL)
	{
		(*ptr)->first = newnode;
		(*ptr)->last = newnode;
		(*ptr)->last->next = (*ptr)->first;
		(*ptr)->number++;
		newnode->prev = newnode->next = NULL;
	}
	else
	{
		newnode->prev = (*ptr)->last;
		(*ptr)->last->next = newnode;
		(*ptr)->last = newnode;
		(*ptr)->last->next = (*ptr)->first;
		(*ptr)->number++;
	}
	return 0;
}

int bilist_insert_order(Head_st **ptr,bilist_st *newnode)
{
	if(*ptr == NULL || newnode == NULL)
		return -1;
	if((*ptr)->first == NULL)
	{
		(*ptr)->first = newnode;
		(*ptr)->last = newnode;
	}
	else
	{
		bilist_st *cur = (*ptr)->first;
		do{
			if(cur->data > newnode->data)
				break;
			else
				cur = cur->next;
			//如果cur等于ptr的first，代表链表将进行2次循环，应将cur置空，插入尾部			
			if(cur == (*ptr)->first)
			{
				cur = NULL;
				break;
			}

		}while(cur != (*ptr)->first);
		if(cur == NULL)
		{
			newnode->prev = (*ptr)->last;
			(*ptr)->last->next = newnode;
			(*ptr)->last = newnode;
		}
		else
		{
			if(cur == (*ptr)->first)
			{
				newnode->next = (*ptr)->first;
				(*ptr)->first->prev = newnode;
				(*ptr)->first = newnode;
			}
			else
			{
				newnode->prev = cur->prev;
				newnode->next = cur;
				newnode->prev->next = newnode;
				newnode->next->prev = newnode;
			}

		}
	}
	(*ptr)->last->next = (*ptr)->first;
	(*ptr)->number++;
	return 0;
}

bilist_st *bilist_find(Head_st *ptr,const Datatype data)
{
	bilist_st *p = ptr->first;
	while(p != ptr->last)
	{
		if(p->data == data)
		{
			return p;
		}
		else
		{
			p = p->next;
		}	
	}
	//排除最后一个元素等于data
	//排除只有一个元素	
	if(ptr->last->data == data)
		return ptr->last;
	else if(ptr->first->data == data)
		return ptr->first;
	return NULL;
}


void bilist_delete(Head_st **ptr,const Datatype data)
{
	bilist_st *p = NULL;
	p = bilist_find(*ptr,data);
	if(p)
	{
		if(p == (*ptr)->first)
		{
			if(p->next)
				(*ptr)->first = p->next;
			else
				(*ptr)->first = NULL;
		}

		else
		{
			if(p == (*ptr)->last)
			{
				(*ptr)->last = p->prev;
			}
			else
			{
				p->prev->next = p->next;
				p->next->prev = p->prev;
			}
		}
		free(p);

	}
}


void bilist_display(Head_st *ptr)
{
	if(ptr->first == NULL)
		return ;
	bilist_st *p;
	for(p = ptr->first;p != ptr->last;p = p->next)
	{
		//		fflush(NULL);
		//		sleep(1);
		printf("%d ",p->data);
	}
	//打印最后一个元素	
	printf("%d\n",ptr->last->data);
}


void bilist_distory(Head_st *ptr)
{
	if(ptr->first == NULL)
		return ;
	bilist_st *p,*q;
	for(p = ptr->first;p != ptr->last;p = q)
	{
		q = p->next;
		free(p);
	}
	free(ptr->last);
	free(ptr);
}


